#include "../tools.h"
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxHeight(vector<vector<int>>& cuboids) {
        for(auto& cub: cuboids)
            sort(cub.begin(), cub.end());
        // 满足拓扑关系即可 a[0] >= b[0] && a[1] >= b[1]
        sort(cuboids.begin(), cuboids.end(), [](const vector<int>& a, const vector<int>& b){
            return a[2] != b[2] ? a[2] > b[2] : (a[0] + a[1]) > b[0] + b[1];
        });
        int size = cuboids.size();
        vector<int> dp(size, 0);
        for(int i = 0; i < size; ++i){
            for(int j = 0; j < i; ++j){
                // cout << i << " " << j << "：" <<  cuboids[j][0] << "-" << cuboids[i][0] << " " << cuboids[j][1] << "-" << cuboids[i][1] << endl;
                if(cuboids[j][0] >= cuboids[i][0] && cuboids[j][1] >= cuboids[i][1] && cuboids[j][2] >= cuboids[i][2]) // 
                {
                    dp[i] = max(dp[i], dp[j]);
                }    
            }
            dp[i] += cuboids[i][2];
        }
        
        return *max_element(dp.begin(), dp.end());
    }
};

int main(int argc, char const *argv[])
{
    Solution sol;

    // vector<vector<int>> cuboids = {{50,45,20},{95,37,53},{45,23,12}};
    // vector<vector<int>> cuboids = {{38,25,45},{76,35,3}};
    vector<vector<int>> cuboids = {{7,11,17},{7,17,11},{11,7,17},{11,17,7},{17,7,11},{17,11,7}};
    int res = sol.maxHeight(cuboids);

    cout << res << endl;


    return 0;
}

